#include <stdio.h>

void MyFastsort(int *a,int start,int end)
{
    if(start >= end)
    return;
    int temp = a[start];
    int left = start;
    int right = end;

    while(left < right)
    {
        while(left < right && a[right] > temp)
        {
            right--;   // 不能一直减，会跳出外循环
        }
        if(left < right)
        {
            a[left] = a[right];
            left++;
        }

        while(left < right && a[left] <  temp)
        {
            left++;
        }

        if(left < right)
        {
            a[right] = a[left];
            right--;
        }
    }
    a[left] = temp;
    //递归排序
    MyFastsort(a,start,left-1);
    MyFastsort(a,right+1,end);
}

void PrintArray(int *s,int len)
{
    for(int i = 0; i < len; i++)
    {
        printf("%d ",s[i]);
    }
    printf("\n");
}

int FindElementByIndex(int *a,int len,int target)
{
    for(int i = 0; i < len; i++)
    {
        if(a[i] == target)
        return i;
    }
    return -1;
}

int BinaryFind(int *a,int len,int target)
{
    int left = 0;
    int right = len-1;
    while(left <= right)
    {
        int mid = left + (right - left) / 2;
        if(target == a[mid])
        return mid;
        if(target > a[mid])
        left = mid +1;
        if(target < a[mid])
        right = mid -1;
    }
    return -1;
} 

int main()
{
    int a[] = {9,4,5,3,2,10};
    MyFastsort(a,0,sizeof(a)/4-1);
    PrintArray(a,sizeof(a)/4);
    printf("%d\n",BinaryFind(a,sizeof(a)/4,5));
}